一种改进的BMH模式匹配算法

分析了目前网络上最流行的BM算法及其改进算法BMH,在此基础上提出了BMH算法的改进算法BMH2。考虑了模式串自身的特征,在原有移动距离数组的基础上增加一个新的移动数组,从而充分利用模式串特征进行更大距离的移动,使算法获得更高的效率。实验证明,改进后的算法能够增加"坏字符"方法的右移量,有效地提高匹配速率。

一种改进的RM可调度性判定算法

固定优先级任务可调度性判定是实时系统调度理论研究的核心问题之一.目前已有的各种判定方法可归结为两大类:多项式时间调度判定和确切性判定.多项式时间调度判定通常采用调度充分条件来进行,为此,许多理想条件下基于RM(rate monotonic)调度算法的CPU利用率最小上界被提了出来.确切性判定利用RM调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的.但是由于时间复杂度较差,确切性判定方法难以实现在线分析.提出了一种改进的RM可调度性判定方法(improved schedulability test algorithm,简称ISTA).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高.

地形可视性分析中观察点设置问题研究

观察点设置问题是地形可视性分析中的一类重要问题，对该问题的研究可以在空间信息辅助决策、通信、旅游、野生动物保护等领域发挥重大作用。本文在对地形可视性分析中观察点设置问题现有研究成果总结和分析基础上对该问题展开深入研究。 首先，针对现有解决方法只从智能算法或地形数据表示方法单一角度进行分析和研究的局限性，提出了一种问题相关的智能算法和数据表示方法相结合的解决问题新框架。该框架考虑了解决观察点设置问题时智能算法的优点和数据表示方式的特点相互配合问题，目的是充分发挥二者各自的优势以提高观察点设置问题解决的准确度与效率。 其次，在深入分析观察点设置问题本身特点的基础上，结合隶属云理论的基本理论和方法，对经典模拟退火算法从退温函数设计、温度产生过程、状态生成过程三方面进行了问题相关的改进，提出了一种适于观察点设置问题的改进模拟退火算法(Improved Simulated Annealing algorithm, ISA)。该算法一方面保持了经典模拟退火算法的稳定倾向特性，保证了算法满足伴随退火温度的不断下降，对恶化的新状态越来越难于接受这一模拟退火算法的最基本特征；另一方面其退火温度的连续性随机变化特性和隐含的“回火升温”过程，则有利于算法有效拒绝恶化解，加速算法收敛，能够更好地满足观察点设置问题对于算法收敛速度的要求。 再次，在分析地形数据的精度、误差等因素对观察点设置问题的解决准确性和解决效率影响程度的基础上，提出了一种基于离散余弦变换的地形数据内插方法(Discrete Cosine Transformation Interpolation method, DCTI)。新方法将传统空域上的地形内插转换到变换域上进行，同时充分利用了离散余弦变换的熵保持特性和能量压缩特性，简化了变换域上的内插过程，提高了地形数据内插的效率和精度。DCTI方法与其他现有典型地形数据内插方法相比，对地形可视性信息获取的准确性和效率影响最小，为平衡观察点设置问题解决过程中时间效率和准确度之间的关系，最终有效地解决观察点设置问题提供了数据基础。 最后，从智能算法和地形数据相结合的角度出发，提出了一种基于ISA和DCTI相结合的观察点设置问题多分辨率处理方法(Multi-Resolution Processing method, MRP)。新方法将模拟退火算法的逐次退火特点和地形数据的多分辨率表示充分结合，达到了发挥算法数据相结合的综合优势的目的。与现有单纯基于模拟退火算法的解决方法相比，在问题解决准确度保持不变的前提下，基于MRP方法的观察点设置问题解决的平均耗时减少85%~95%，为实际工程应用问题的解决提供了一条重要途径。

基于模拟退火算法的挤出模参数优化

建立了塑料熔体在异型材挤出机头流道中的流动均匀性模型 ,阐明了模具结构参数与流动均匀性间的关系,确定了塑料挤出模优化设计的目标函数和设计变量 ,并将一种改进的模拟退火算法用于流线型塑料异型材挤出机头的优化设计。实例表明所用方法对挤出模优化设计的适用性,该方法在利用经验的同时 ,优化了模具结构参数 ,提高了模具设计的智能化

青藏高原及邻区面波频散反演--岩石圈-软流层体系结构研究

The Qinghai-Tibet Plateau lies in the place of the continent-continent collision between Indian and Eurasian plates. Because of their interaction the shallow and deep structures are very complicated. The force system forming the tectonic patterns and driving tectonic movements is effected together by the deep part of the lithosphere and the asthenosphere. It is important to study the 3-D velocity structures, the spheres and layers structures, material properties and states of the lithosphere and the asthenosphere for getting knowledge of their formation and evolution, dynamic process, layers coupling and exchange of material and energy. Based on the Rayleigh wave dispersion theory, we study the 3-D velocity structures, the depths of interfaces and thicknesses of different layers, including the crust, the lithosphere and the asthenosphere, the lithosphere-asthenosphere system in the Qinghai-Tibet Plateau and its adjacent areas. The following tasks include: (1)The digital seismic records of 221 seismic events have been collected, whose magnitudes are larger than 5.0 over the Qinghai-Tibet Plateau and its adjacent areas. These records come from 31 digital seismic stations of GSN , CDSN、NCDSN and part of Indian stations. After making instrument response calibration and filtering, group velocities of fundamental mode of Rayleigh waves are measured using the frequency-time analysis (FTAN) to get the observed dispersions. Furthermore, we strike cluster average for those similar ray paths. Finally, 819 dispersion curves (8-150s) are ready for dispersion inversion. (2)From these dispersion curves, pure dispersion data in 2°×2° cells of the areas (18°N-42°N, 70°E-106°E) are calculated by using function expansion method, proposed by Yanovskaya. The average initial model has been constructed by taking account of global AK135 model along with geodetic, geological, geophysical, receiving function and wide-angle reflection data. Then, initial S-wave velocity structures of the crust and upper mantle in the research areas have been obtained by using linear inversion (SVD) method. (3)Taking the results of the linear inversion as the initial model, we simultaneously invert the S wave velocities and thicknesses by using non-linear inversion (improved Simulated Annealing algorithm). Moreover, during the temperature dropping the variable-scale models are used. Comparing with the linear results, the spheres and layers by the non-linear inversion can be recognized better from the velocity value and offset. (4)The Moho discontinuity and top interface of the asthenosphere are recognized from the velocity value and offset of the layers. The thicknesses of the crust, lithosphere and asthenosphere are gained. These thicknesses are helpful to studying the structural differentia between the Qinghai-Tibet Plateau and its adjacent areas and among geologic units of the plateau. The results of the inversion will provide deep geophysical evidences for studying deep dynamical mechanism and exploring metal mineral resource and oil and gas resources. The following conclusions are reached by the distributions of the S wave velocities and thicknesses of the crust, lithosphere and asthenosphere, combining with previous researches. (1)The crust is very thick in the Qinghai-Tibet Plateau, varying from 60 km to 80 km. The lithospheric thickness in the Qinghai-Tibet Plateau is thinner (130-160 km) than its adjacent areas. Its asthenosphere is relatively thicker, varies from 150 km to 230 km, and the thickest area lies in the western Qiangtang. India located in south of Main Boundary thrust has a thinner crust (32-38 km), a thicker lithosphere of about 190 km and a rather thin asthenosphere of only 60 km. Sichuan and Tarim basins have the crust thickness less than 50km. Their lithospheres are thicker than the Qinghai-Tibet Plateau, and their asthenospheres are thinner. (2)The S-wave velocity variation pattern in the lithosphere-asthenosphere system has band-belted distribution along east-westward. These variations correlate with geology structures sketched by sutures and major faults. These sutures include Main Boundary thrust (MBT), Yarlung-Zangbo River suture (YZS), Bangong Lake-Nujiang suture (BNS), Jinshajiang suture (JSJS), Kunlun edge suture (KL). In the velocity maps of the upper and middle crust, these sutures can be sketched. In velocity maps of 250-300 km depth, MBT, BNS and JSJS can be sketched. In maps of the crustal thickness, the lithospheric thickness and the asthenospheric thickness, these sutures can be still sketched. In particular, MBT can be obviously resolved in these velocity maps and thickness maps. (3)Since the collision between India and Eurasian plate, the “loss” of surface material arising from crustal shortening is caused not only by crustal thickening but also by lateral extrusion material. The source of lateral extrusion lies in the Qiangtang block. These materials extrude along the JSJS and BNS with both rotation and dispersion in Daguaiwan. Finally, it extends toward southeast direction. (4)There is the crust-mantle transition zone of no distinct velocity jump in the lithosphere beneath the Qiangtang Terrane. It has thinner lithosphere and developed thicker asthenosphere. It implies that the crust-mantle transition zone of partial melting is connected with the developed asthenosphere. The underplating of asthenosphere may thin the lithosphere. This buoyancy might be the main mechanism and deep dynamics of the uplift of the Qinghai-Tibet hinterland. At the same time, the transport of hot material with low velocity intrudes into the upper mantle and the lower crust along cracks and faults forming the crust-mantle transition zone.

An improved BP algorithm for pattern recognition

An improved BP algorithm for pattern recognition is proposed in this paper. By a function substitution for error measure, it resolves the inconsistency of BP algorithm for pattern recognition problems, i.e. the quadratic error is not sensitive to whether the training pattern is recognized correctly or not. Trained by this new method, the computer simulation result shows that the convergence speed is increased to treble and performance of the network is better than conventional BP algorithm with momentum and adaptive step size.

A block SPP algorithm for multidimensional tridiagonal equations with optimal message vector length

A parallel strategy for solving multidimensional tridiagonal equations is investigated in this paper. We present in detail an improved version of single parallel partition (SPP) algorithm in conjunction with message vectorization, which aggregates several communication messages into one to reduce the communication cost. We show the resulting block SPP can achieve good speedup for a wide range of message vector length (MVL), especially when the number of grid points in the divided direction is large. Instead of only using the largest possible MVL, we adopt numerical tests and modeling analysis to determine an optimal MVL so that significant improvement in speedup can be obtained.

On optimal message vector length for block single parallel partition algorithm in a three-dimensional ADI solver

It has long been recognized that many direct parallel tridiagonal solvers are only efficient for solving a single tridiagonal equation of large sizes, and they become inefficient when naively used in a three-dimensional ADI solver. In order to improve the parallel efficiency of an ADI solver using a direct parallel solver, we implement the single parallel partition (SPP) algorithm in conjunction with message vectorization, which aggregates several communication messages into one to reduce the communication costs. The measured performances show that the longest allowable message vector length (MVL) is not necessarily the best choice. To understand this observation and optimize the performance, we propose an improved model that takes the cache effect into consideration. The optimal MVL for achieving the best performance is shown to depend on number of processors and grid sizes. Similar dependence of the optimal MVL is also found for the popular block pipelined method.

MODIFIED DIRECT TWOS-COMPLEMENT PARALLEL ARRAY MULTIPLICATION ALGORITHM FOR COMPLEX MATRIX OPERATION

A direct twos-complement parallel array multiplication algorithm is introduced and modified for digital optical numerical computation. The modified version overcomes the problems encountered in the conventional optical twos-complement algorithm. In the array, all the summands are generated in parallel, and the relevant summands having the same weights are added simultaneously without carries, resulting in the product expressed in a mixed twos-complement system. In a two-stage array, complex multiplication is possible with using four real subarrays. Furthermore, with a three-stage array architecture, complex matrix operation is straightforwardly accomplished. In the experiment, parallel two-stage array complex multiplication with liquid-crystal panels is demonstrated.

A reliable phase unwrapping algorithm based on the local fitting plane and quality map

A fast and reliable phase unwrapping (PhU) algorithm, based on the local quality-guided fitting plane, is presented. Its framework depends on the basic plane-approximated assumption for phase values of local pixels and on the phase derivative variance (PDV) quality map. Compared with other existing popular unwrapping algorithms, the proposed algorithm demonstrated improved robustness and immunity to strong noise and high phase variations, given that the plane assumption for local phase is reasonably satisfied. Its effectiveness is demonstrated by computer-simulated and experimental results.

Algorithm of far-field centre estimation based on phase-only matched filter

Estimation of the far-field centre is carried out in beam auto-alignment. In this paper, the features of the far-field of a square beam are presented. Based on these features, a phase-only matched filter is designed, and the algorithm of centre estimation is developed. Using the simulated images with different kinds of noise and the 40 test images that are taken in sequence, the accuracy of this algorithm is estimated. Results show that the error is no more than one pixel for simulated noise images with a 99% probability, and the stability is restricted within one pixel for test images. Using the improved algorithm, the consumed time is reduced to 0.049 s.

The design algorithm of an associative memory neural network

A design algorithm of an associative memory neural network is proposed. The benefit of this design algorithm is to make the designed associative memory model can implement the hoped situation. On the one hand, the designed model has realized the nonlinear association of infinite value pattern from n dimension space to m dimension space. The result has improved the ones of some old associative memory neural network. On the other hand, the memory samples are in the centers of the fault-tolerant. In average significance the radius of the memory sample fault-tolerant field is maximum.